package Sort_06;

/*
 * @Author 罗
 * @date 2020/3/18 - 8:19 下午
 *  基数排序的说明:
    (1)基数排序是对传统桶排序的扩展，速度很快.
    (2)基数排序是经典的空间换时间的方式，占用内存很大, 当对海量数据排序时，容易造成 OutOfMemoryError 。
    (3)基数排序时稳定的。[注:假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的]
    (4)有负数的数组，我们不用基数排序来进行排序, 如果要支持负数，参考: https://code.i-harness.com/zh-CN/q/e98fa9

 */

import org.junit.Test;

import java.util.Arrays;

public class RadixSort_08 {

    @Test
    public void test() {
        int[] array = {53, 3, 542, 748, 14, 214};

        radixSort(array);

        System.out.println(Arrays.toString(array));
    }

    /**
     * 桶排序
     * 空间换取时间
     * 对传统桶排序的扩展
     * 是稳定排序，数值相同的元素，排序之后相对位置不变
     * 不能处理负数，如果强行处理负数，需要改进
     * 如果需要排序80 000 000 条数据，需要10个桶，每个int占4 byte
     * 需要80 000 000 * 11 * 4 /1024/1024/1024 = 3.4GB  内存
     * @param array
     */
    public static void radixSort(int[] array) {

        /*
         * 1.定义一个二维数组，表示10个桶，每个桶就是一个一维数组
         *      (1)一个二维数组包含10个一维数组，每一个一维数组就是一个桶
         *      (2)为了防止在放入数的时候，数据溢出
         *           在每一个桶（一维数组）的大小定义 为 array.length
         *          （数组的所有数个位都是1），第一次放入桶的时候就要将数组全部放在一个桶里
         *      (3)明确：基数排序是使用空间换取时间的经典算法
         * */
        int[][] buckets = new int[10][array.length];

        /*
         *  为了记录每个桶中，实际放了多少数据
         *  定义一个一维数组来记录每个桶中当前有多少条数据
         * */
        int[] bucketElementCounts = new int[10];
        /*
         * 假设最大值是array[0]
         * */
        int maxValue = array[0];
        /*
         * 得出最大值
         * */
        for (int i : array) {
            if (i > maxValue) {
                maxValue = i;
            }
        }
        /*
         * 获取最大值的位数
         *      一个投机取巧的办法
         * */
        int maxBitLength = String.valueOf(maxValue).length();
        /*
         * 针对每个元素的对应位进行处理
         * 按照个位、十位、百位、千位.... 的大小，依次将元素放入桶中
         * */
        for (int bit = 0; bit < maxBitLength; bit++) {

            /*
             * 将数组中的所有元素放入桶中
             * */
            for (int i = 0; i < array.length; i++) {
                /*
                 * 取出数组元素的个位、十位、千位...
                 * 个位 = 198  / 1    % 10
                 * 十位 = 198  / 10   % 10
                 * 千位 = 1999 / 100  % 10
                 * 万位 = 14423/ 1000 % 10
                 * */
                int digitOfElement = array[i] / (int) Math.pow(10, bit) % 10;
                /*
                 * 将取出的元素根据取出元素的个位(digitOfElement)放在 指定的桶中
                 *       放在该桶中还没有写入数据的地方bucketElementCounts [ digitOfElement ]
                 * */
                buckets[digitOfElement][bucketElementCounts[digitOfElement]] = array[i];

                bucketElementCounts[digitOfElement]++;
            }
            /*
             * 原始数组的指针
             * */
            int originElementIndex = 0;
            /*
             * 按照桶的顺序（二维数组的下标）将桶中的数据取出，放入到原数组中
             * 遍历每个桶
             * */
            for (int i = 0; i < buckets.length; i++) {
                /*
                 * for循环自带if条件判断
                 * 将桶中的元素遍历
                 * */
                for (int j = 0; j < bucketElementCounts[i]; j++) {
                    /*
                     * 将桶中的元素放入原始数组
                     * */
                    array[originElementIndex] = buckets[i][j];
                    /*
                     * 将原始的一维数组指针后移，以赋值排序后的元素
                     * */
                    originElementIndex++;
                }
                /*
                 * 将每个桶的数据指针移动到0
                 * */
                bucketElementCounts[i] = 0;
            }
//            System.out.println("第"+(bit+1)+"轮排序的结果\t"+Arrays.toString(array));
        }
    }
}
